
class Graph(object):
	"""docstring for Graph"""
	def __init__(self, arg):
		super(Graph, self).__init__()
		self.number = arg
		self.dist = [[99999999 for i in range(self.number)] for i in range(self.number)]
		for i in range(self.number):
			self.dist[i][i]=0
		self.shortest = [[99999999 for i in range(self.number)] for i in range(self.number)]
		for i in range(self.number):
			self.shortest[i][i]=0
		self.next = [[-1 for i in range(self.number)] for i in range(self.number)]
	def addPath(self,x,y,l):
		self.dist[x][y] = l
		self.dist[y][x] = l
		self.shortest[x][y] = l
		self.shortest[y][x] = l
		pass
	def calcShortest(self):
		for k in range(self.number):
			for i in range(self.number):
				for j in range(i+1,self.number):
					if self.dist[i][k] != 0 and self.dist[i][k] + self.shortest[k][j] <= self.shortest[i][j]:
						self.shortest[i][j] = self.dist[i][k] + self.shortest[k][j]
						self.next[i][j] = k
		pass
	def shortestNumber(self,x,y):
		ans = 0
		n = 0
		l = []
		for i in range(self.number):
			if i != x and self.dist[i][x] + self.shortest[i][y] == self.shortest[x][y]:
				n +=1
				l.append(i)
		for i in l:
			ans += 
		pass
def main():
	g = Graph(5)
	g.addPath(0,1,1)
	g.addPath(0,2,2)
	g.addPath(0,3,1)
	g.addPath(1,2,1)
	g.addPath(2,4,1)
	g.addPath(3,4,1)
	print g.dist
	print g.shortest
	g.calcShortest()
	print g.shortest
	pass

if __name__ == '__main__':
	main()
		